0050. Pow(x, n)【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 快速幂（迭代）
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

实现 pow(x, n)，即计算 x 的整数 n 次幂函数（即，$x^n$ ）。

---

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

---

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

---

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000

解释：$2^{-2}=1/2^2=1/4=0.25$

---

提示：

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0。
• -10^4 <= x^n <= 10^4

2. 🎯 s.1 - 快速幂（迭代）

c

double myPow(double x, int n) {
    long long N = n; // 避免 n = INT_MIN 时取反溢出
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    double result = 1.0;
    while (N > 0) {
        if (N & 1)
            result *= x; // 当前位为 1，累乘当前底数
        x *= x;          // 底数平方
        N >>= 1;
    }
    return result;
}

js

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (n < 0) {
    x = 1 / x
    n = -n
  }
  let result = 1
  while (n > 0) {
    if (n % 2 === 1) result *= x // 当前位为 1，累乘当前底数
    x *= x // 底数平方
    n = Math.floor(n / 2)
  }
  return result
}

py

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1
        while n > 0:
            if n & 1:
                result *= x  # 当前位为 1，累乘当前底数
            x *= x  # 底数平方
            n >>= 1
        return result

• 时间复杂度：$O(\log n)$，每次将指数右移一位（除以 2），最多循环 $\log n$ 次
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 若 n < 0，将问题转化为 $x^{-n}$ 的倒数，即令 x = 1/x, n = -n
• 利用指数的二进制表示拆分幂运算，例如 $x^{13}=x^{(1101{)}_2}=x^8\cdot x^4\cdot x^1$
• 每轮检查 n 的最低位，若为 1 则将当前底数累乘到结果中，然后底数自乘（平方），指数右移一位
• C 语言中使用 long long 存储指数，避免 $n=-2^{31}$ 取反溢出

3. 🔗 引用

• C++ pow() 函数